Neural Information Processing Systems http://nips.cc/

Network theory studies the interaction of connected systems of agents.

ABSTRACT Regularization of the classical Laplacian matrices was empirically shown to improve spectral clustering in sparse networks. It was observed that small regularizations are preferable, but this point was left as a heuristic argument. In this paper we formally determine a proper regularization which is intimately related to alternative state-of-the-art spectral techniques for sparse graphs. Index T erms-- Regularized Laplacian, Bethe-Hessian, spectral clustering, sparse networks, community detection 1. INTRODUCTION Community detection [1] is one of the central unsupervised learning tasks on graphs. The community detection problem has vast applications in different fields of science [2] and can be seen as the simplest form of clustering, i.e. the problem of dividing objects into similarity classes.

Spectral clustering is one of the most popular, yet still incompletely understood, methods for community detection on graphs. In this article we study spectral clustering based on the deformed Laplacian matrix $D-rA$, for sparse heterogeneous graphs (following a two-class degree-corrected stochastic block model). For a specific value $r = \zeta$, we show that, unlike competing methods such as the Bethe Hessian or non-backtracking operator approaches, clustering is insensitive to the graph heterogeneity. Based on heuristic arguments, we study the behavior of the informative eigenvector of $D-\zeta A$ and, as a result, we accurately predict the clustering accuracy. Via extensive simulations and application to real networks, the resulting clustering algorithm is validated and observed to systematically outperform state-of-the-art competing methods.